namespace AddTwoNumbers
{
    public class ListNode
    {
        public ListNode next;
        public int val;

        public ListNode(int x)
        {
            val = x;
        }
    }


    public class Solution
    {
        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
        {
            // 进位
            var carry = 0;
            // 结果
            var sum = new ListNode(0);
            // 中间指针
            var head = sum;

            while (true)
            {
                carry += l1.val + l2.val;
                head.val = carry % 10;
                carry /= 10;

                l1 = l1.next;
                l2 = l2.next;

                if (l1 == null || l2 == null) break;

                head.next = new ListNode(0);
                head = head.next;
            }


            var surplus = l1 == null ? l2 : l1;

            while (surplus != null)
            {
                head.next = new ListNode(0);
                head = head.next;

                carry += surplus.val;
                head.val = carry % 10;
                carry /= 10;

                surplus = surplus.next;
            }

            if (carry == 0)
                return sum;

            head.next = new ListNode(0);
            head = head.next;
            head.val = carry;
            return sum;
        }
    }
}